/**
 * 
 */
package array.passed;

/**
 * @author xyyi
 *
 */
public class SearchinRotatedSortedArray {

	/**
	Suppose a sorted array is rotated at some pivot unknown to you beforehand.

	(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

	You are given a target value to search. If found in the array return its index, otherwise return -1.

	You may assume no duplicate exists in the array.
	 */

	public int search(int[] A, int target) {
		if (A == null || A.length == 0)
			return -1;
		int left = 0, right = A.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;// avoid overflow
			if (target == A[mid]) {
				return mid;
			}
			// left to mid is ASC order
			if (A[mid] >= A[left]) {
				if (target < A[mid] && target >= A[left])
					right = mid - 1;
				else
					left = mid + 1;
			}
			// mid to right is ASC order
			else { // A[mid] > A[left], 
				if (target > A[mid] && target <= A[right])
					left = mid + 1;
				else
					right = mid - 1;
			}
		}

		return -1;
	}

	public int searchalternative(int[] A, int target) {

		if (A == null || A.length == 0)
			return -1;

		int left = 0, right = A.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (A[mid] == target)
				return mid;
			if (A[mid] >= A[0]) {
				if (target < A[mid] && target >= A[0])
					right = mid - 1;
				else
					left = mid + 1;
			} else {
				if (target > A[mid] && target <= A[A.length - 1])
					left = mid + 1;
				else
					right = mid - 1;
			}
		}

		return -1;
	}

	/**
	 * 
	 */
	public SearchinRotatedSortedArray() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
